/*
Graph coloring algorithm
created by psych0der on 14th April 2012
copyright (c) psych0der
nobles0ul@me.com

*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int matrix[6][6]; // adjacency matrix for the graph
int color[6]; // matrix to store color of each vertex
int state[6]; // stores the state of vertex during dfs

void readFile(void);
int assignColor(void);
int applycolor(int);

int main()
{
	int i,j; // loop counters
	int state;// graph is colorable or not
	readFile(); // inintialize adjacency matrix
	
	
	
	/*  display the matrix found */
	printf("\n");
	for( i=0;i<6;i++)
	{
		for( j=0;j<6;j++)
		{
			printf("%d-",matrix[i][j]);
		}
		printf("\n");
	}
	for(i=0;i<6;i++)
		color[i] = -10; // initialize all vertices to invalid color
		
	state = assignColor();
	
	if(state==-1)
	{
		printf("\n the graph provided is not colorable \n");
	}
	
	else
	{
		printf("\n the graph is colorable with following color");
		for(i=0;i<6;i++)
		{
			switch(color[i])
			{
				
			case 0:
			{
				printf(" %d - red",i);
				break;
			}	
			
			case 1:
			{
				printf(" %d - blue",i);
				break;
			}
			case 2:
			{
				printf(" %d - green",i);
				break;
			}
			
			default :
			{
				printf(" %d - blue",i);
			}

			}

		}
	}
	
	return 0;
	
}

void readFile(void)
{
    FILE *file1;
	int i,j;
	
		
	if((file1 = fopen("adjacencylist.txt","r")) == NULL)
	{
		printf("\n File could'nt be opened");
	}
	else
	{
		// placeholder for else function
	}
	
	for( i=0;i<6;i++)
	{
		for(j=0;j<6;j++)
		{
			fscanf(file1,"%d",&matrix[i][j]);
		}
	}
    	
	
}

int assignColor(void)
{
	int i,j,k; //loop counters
	int indicator; // to verify if graph is colorable or not
	
	
	
	for(i=0;i<6;i++)
	{
		indicator = applycolor(i);
		if(indicator == -1)
		{
			return -1;
		}
	}
	return 1;
	
}

int applycolor(int a)
{
	/*
	flag0 : this indicates that color is already used
	flag1 : this indicates that a vertex is sucessfully colored
	flag2 : this means that graph is not 3 colorable
	
	
	
	
	*/
	
	
	
	
	int flag0,flag1,flag2; // flags for loop breaks
	int i,j;
	int colorn=0;
	flag0 = flag1 = 0;
	flag2= 1;
	
	
	for(i=0;i<3;i++)
	{
		for(j=0;j<6;j++)
		{
		 
		  
			if(matrix[a][j] ==1)
			{
				if(color[j]==colorn)
				{
					flag0 = 1;
					break;
				}
			}
		  
		  
		
		}
	
		
		
		if(flag0==1)
		{
			flag0=0; // reset flag0 .. this means color not available
			colorn++; // check for next color
			flag2++;
			continue;
		}
		
		else
		{
			flag1 = 1;
			color[a] = colorn; // apply color to vertex
			break;
		}
		
	}
	
	if(flag2==3)
	{
		return -1;
	}
	
	if(flag1 == 1)
	{
		return 1;
	}




}



